/*https://leetcode.cn/problems/delete-and-earn/submissions/562792907/
删除并获得点数
24/9/7
*/

class Solution {
public:
    const int MAX_VALUE = 1e4 + 5; // 定义一个足够大的值，以确保可以包含输入数组中可能出现的所有正整数

    int deleteAndEarn(vector<int>& nums) {
        vector<int> frequency(MAX_VALUE, 0); // 用于统计每个数字出现的频率
        vector<int> value(MAX_VALUE, 0); // 记录每个数字的实际值，虽然这里实际上可以简化为数字本身
        vector<vector<int>> dp(MAX_VALUE, vector<int>(2, 0)); // 动态规划表，dp[i][0]表示不删除i时的最大收益，dp[i][1]表示删除i时的最大收益

        // 统计每个数字出现的次数
        for (int num : nums) {
            frequency[num]++;
            value[num] = num; // 实际上这里的value[num]总是等于num，因为value数组只是用来标记数字的存在
        }

        // 动态规划求解
        for (int i = 1; i < MAX_VALUE; i++) {
            if (value[i] > 0) { // 如果数字i存在
                // 不删除数字i的情况：最大收益为前一个数字的最大收益（无论是删除还是不删除）
                dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);

                // 删除数字i的情况：最大收益为不删除前一个数字的最大收益加上删除当前数字i的收益
                if (value[i - 1] > 0) { // 如果前一个数字存在
                    dp[i][1] = dp[i - 1][0] + frequency[i] * value[i];
                } else { // 如果前一个数字不存在，可以直接从前一个数字的两种状态中选择最大值
                    dp[i][1] = max(dp[i - 1][0], dp[i - 1][1]) + frequency[i] * value[i];
                }
            } else { // 如果当前数字i不存在
                // 直接继承前一个数字的最大收益
                dp[i][0] = dp[i][1] = max(dp[i - 1][0], dp[i - 1][1]);
            }
        }

        // 最终结果为考虑所有数字后，删除或不删除最后一个数字的最大收益
        return max(dp[MAX_VALUE - 1][0], dp[MAX_VALUE - 1][1]);
    }
};